package com.mccken.practice.top100.Top_1$20.Top_17;

import java.util.ArrayList;
import java.util.List;

/**
 * 顺时针螺旋
 *
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-01-06 14:41
 **/
public class SpiralOrder {

	public List<Integer> spiralOrder1(int[][] matrix) {
		List<Integer> order = new ArrayList<>();

		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return order;
		}

		int rows = matrix.length;
		int columns = matrix[0].length;

		int left = 0, right = columns - 1, top = 0, bottom = rows - 1;

		while (left <= right && top <= bottom) {
			// 在top层，从左到右遍历
			for (int x = left; x <= right; x++) {
				order.add(matrix[top][x]);
			}

			// 在right层，从上往下遍历
			for (int y = top + 1; y <= bottom; y++) {
				order.add(matrix[y][right]);
			}

			if (left < right && top < bottom) {
				// 在 bottom层，从右往左遍历
				for (int x = right - 1; x > left; x--) {
					order.add(matrix[bottom][x]);
				}

				for (int y = bottom; y > top; y--) {
					order.add(matrix[y][left]);	
				}
			}
			
			left++;
			right--;
			top++;
			bottom--;
		}

		return order;
	}

	public List<Integer> spiralOrder(int[][] matrix) {
		List<Integer> order = new ArrayList<>();

		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return order;
		}

		int rows = matrix.length;
		int columns = matrix[0].length;

		boolean[][] visited = new boolean[rows][columns];
		int total = rows * columns;

		// 方向
		int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
		int directionIndex = 0;

		int row = 0, column = 0;
		for (int i = 0; i < total; i++) {
			order.add(matrix[row][column]);
			visited[row][columns] = true;

			int nextRow = row + directions[directionIndex][0];
			int nextColumn = column + directions[directionIndex][1];

			// 遇到边界或者遇到需要已访问过的元素
			if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
				directionIndex = (directionIndex + 1) % 4;
			}
			row += directions[directionIndex][0];
			column += directions[directionIndex][1];
		}
		return order;
	}
}
